package com.xiaoyu.arrays;

/**
 * @program: DS_and_A
 * @description: 给定一个整数数组 nums ，找到一个具有 最大和 的 连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 *  第一个动态规划的题目!!
 *
 * @author: YuWenYi
 * @create: 2021-04-23 08:56
 **/
public class MaxSubArray_53 {
    /*
        错误解法!
        int n = 1; //子连续数组的元素个数
        int max = 0;
        int sum = 0;
        int len = nums.length;
        //int x = len*(1+len)/2;
        for (int i = 0; i < len*(1+len)/2-1; i++) {
            for (int j = i; j < n; j++) {

                sum = sum + nums[j];
                System.out.println("sum-->"+sum);

                max = sum > max ? sum :max;
                System.out.println(max);
            }
            sum=0;
            System.out.println("----------------");
            n++;
        }
        return max;
    * */
    //也可以考虑思路:如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加。

    //此题动态规划公式：f(n) = max( f(n-1)+nums[n], nums[n]);
    //f(n) --> max    f(n-1) --> sum
    public static int maxSubArray(int[] nums) {
       /*
        贪心算法:
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;


        动态规划求法:
         int pre = 0, maxAns = nums[0];
            for (int x : nums) {
                pre = Math.max(pre + x, x);
                maxAns = Math.max(maxAns, pre);
            }
         return maxAns;
        */

        int max = nums[0];
        int sum = 0;
        for (int num : nums) {  //遍历数组
            if (sum > 0) {
                sum += num;    //如果sum是大于0的,那么就加下一个数 公式--> f(n-1)+nums[n]
            } else {
                sum = num;
            }
            max = Math.max(max, sum);
        }
        return max;
    }

    public static void main(String[] args) {
        /*
        * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
          输出：6
          解释：连续子数组 [4,-1,2,1] 的和最大，为 6
        * */
        int[] nums = new int[]{-1};
        int max = maxSubArray(nums);
        System.out.println("max--->"+max);
    }
}
